package sorts;

import java.util.BitSet;
import java.util.Random;

public class QuickSortII {

    final Integer[] integers = new Integer[]{};
    private static int swapCount = 0;

    private void test(){
        integers[0] = 123;
    }

    private static void swap(int[] arr, int a, int b){
        if(a != b){
            int t = arr[a];
            arr[a] = arr[b];
            arr[b] = t;
        }
        swapCount ++;
    }

    private static int patition(int[] arr, int start, int end){
        int index = (new Random()).nextInt(end - start + 1) + start;
        swap(arr, index, end);
        int small = start - 1;
        for(index = start; index < end; index ++){
            if(arr[index] < arr[end]){
                small ++;
                if(small != index){
                    swap(arr, small, index);
                }
            }
        }
        small ++;
        swap(arr, small, end);
        return small;
    }

    private static void quickSort(int[] arr, int start, int end){
        if(start < end){
            int index = patition(arr, start, end);
            quickSort(arr, start, index - 1);
            quickSort(arr, index + 1, end);
        }

    }

    public static void quickSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 进行数字排序
     */
    public static void sortArray() {
        int[] array = new int[] { 423, 700, 9999, 2323, 356, 6400, 1,2,3,2,2,2,2 };
        BitSet bitSet = new BitSet(2 << 13);
        // 虽然可以自动扩容，但尽量在构造时指定估算大小,默认为64
        System.out.println("BitSet size: " + bitSet.size());

        for (int i = 0; i < array.length; i++) {
            bitSet.set(array[i]);
        }
        //剔除重复数字后的元素个数
//        int bitLen=bitSet.cardinality();

        //进行排序，即把bit为true的元素复制到另一个数组
        int[] orderedArray = new int[array.length];
        int k = 0;
        for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
            orderedArray[k++] = i;
        }
        System.out.println(bitSet);
        System.out.println("After ordering: ");
        for (int i = 0; i < array.length; i++) {
            System.out.print(orderedArray[i] + "\t");
        }

        System.out.println("iterate over the true bits in a BitSet");
        //或直接迭代BitSet中bit为true的元素iterate over the true bits in a BitSet
        for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
            System.out.print(i+"\t");
        }
        System.out.println("---------------------------");
    }

    public static void main(String[] args){
//        int[] nums = new int[]{10,3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};
//        QuickSortII.quickSort(nums);
////        nums = QuickSort.qsort(nums, 0, nums.length - 1);
//        QuickSort.print(nums);
//        System.out.println(swapCount);
//        sortArray();
        int a = Integer.MAX_VALUE - 1;
        a = a + 2;
        System.out.println(a);

        System.out.println(a -1);
        System.out.println(Integer.MIN_VALUE);
    }
}

